package com.yuhuan.sowordtooffer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * 剑指offer 09用两个栈实现队列
 *
 */
public class CQueue {
    LinkedList<Integer> a,b;
    public CQueue() {
        a  = new LinkedList<Integer>();
        b  = new LinkedList<Integer>();

    }

    public void appendTail(int value) {
        a.addLast(value);
    }

    /**
     * 这个方法的目的是删除一个队列的头元素，先进去的那个元素，但是这个队列是用两个栈实现的，因此删除的时候需要将一个栈中的元素倒入另一个栈中，
     * 头元素就会处于栈顶，调用pop()出栈，头元素就被删除了，然后再把b中剩下的元素倒回a栈中，让队列的先后顺序保持不变
     * @return 正常情况是返回删除的那个头元素，如果队列为空，则返回-1
     */
    public int deleteHead() {
        //如果栈a不为空。则将a中的元素，从最后一个出栈，加入b中，直到a为空
        while (!a.isEmpty()){
            b.addLast(a.pop());
        }
        //上面是处理了a为空的情况，那下面就得包含，得考虑是栈a不为空的情况了
        //为什么res默认值为-1，因为如果这个栈中没有元素，则返回-1；很好理解，如果栈a空，栈b也空，那res自然不变了，res=-1
        int res = -1;
        if (!b.isEmpty()) {
            res = b.pop();
        }
        while (!b.isEmpty()){
            a.push(b.pop());
        }
        return res;
    }

    public static void main(String[] args) {
        CQueue test = new CQueue();

        System.out.print("[null,");
        test.appendTail(3);
        System.out.print("null,");
        System.out.print(test.deleteHead()+",");
        test.deleteHead();
        System.out.println(test.deleteHead()+"]");
        test.appendTail(1);
        test.appendTail(5);

        test.appendTail(6);

        while (!test.a.isEmpty()){
            System.out.print(test.a.pop()+" ");
        }


        System.out.println();
        System.out.println("test2执行结果如下：");
        CQueue test2 = new CQueue();
        System.out.print("[null,");
        System.out.print(test2.deleteHead()+",");
        test2.appendTail(5);
        System.out.print("null,");
        test2.appendTail(2);
        System.out.print("null,");

        System.out.print( test2.deleteHead()+",");
        System.out.print(test2.deleteHead()+"]");

        test2.appendTail(3);
        test2.appendTail(3);

        System.out.println();

        while (!test2.a.isEmpty()){
            System.out.print(test2.a.pop()+" ");
        }
    }
}
